β

Как стать автором
Погнали в космос?
Посмотри в Календарь, вдруг сегодня есть мероприятие?

Моя лентаВсе потоки

quasilyte 18 июл 2018 в 01:27

Ускорение конкатенации строк в Go своими руками

8 мин

18K

Assembler*Go*Компиляторы*Программирование*Системное программирование*

Сегодня мы будем разгонять склеивание коротких строк в Go на 30%. Причём для этого нам не нужно будет модифицировать сам Go, всё это будет реализованно в виде сторонней библиотеки.

Под катом вас ждут:

Сравнение +, strings.Builder и собственной функции конкатенации

Детали внутреннего устройства строк в Go

Совсем немного ассемблера

Данную статью можно также считать предлогом обсудить CL123256: runtime,cmd/compile: specialize concatstring2. Идеи по улучшению этого change list'а приветствуются.

Сразу результаты

Сравнение производилось с go tip (master) версией компилятора. Аналогичные результаты вы можете получить на версиях примерно с Go 1.5. Последним значительным изменением функции concatstrings был CL3120: cmd/gc: allocate buffers for non-escaped strings on stack.

BenchmarkConcat2Operator-8 20000000 83.8 ns/op
BenchmarkConcat2Builder-8 20000000 70.9 ns/op
BenchmarkConcat2-8 20000000 62.1 ns/op
BenchmarkConcat3Operator-8 20000000 104 ns/op
BenchmarkConcat3Builder-8 20000000 89.9 ns/op
BenchmarkConcat3-8 20000000 82.1 ns/op

ConcatOperator использует +.

ConcatBuilder использует strings.Builder с правильной пред-аллокацией.

Concat использует функцию, которую мы реализуем в рамках этой истории.

Сравнение через benchstat:

name old time/op new time/op delta
Concat2-8 84.2ns ± 1% 62.7ns ± 2% -25.49% (p=0.000 n=9+10)
Concat3-8 103ns ± 3% 83ns ± 4% -19.83% (p=0.000 n=10+9)

Ассемблерная реализация под GOARCH=AMD64 немного быстрее и обладает дополнительной оптимизацией, которая присутствует у встроенного оператора +, но об этом ниже:

name old time/op new time/op delta
Concat2-8 84.2ns ± 1% 57.1ns ± 3% -32.20% (p=0.000 n=9+9)

Ассемблерную функцию будем брать как 100% производительности (относительно остальных рассматриваемых реализаций).

Результаты для более длинных строк можно увидеть в README.md. Чем длиннее строка, тем менее выражена разница между реализациями.

Наивная конкатенация

Самым простым решением является использование оператора +.

Семантика этого оператора такая: взять две строки и вернуть строку-результат, которая содержит сцепление обеих строк. При этом нет гарантии, что будет возвращена новая строка. Например, если происходит сцепление пустой строки и любой другой, runtime может вернуть непустой аргумент, избегая необходимости выделять новую память и копировать туда данные.

Но, как видно из результатов в начале статьи, это самый медленный способ.

func concat2operator(x, y string) string {
return x + y
}

Оценка производительности: 67.8%.

strings.Builder

Не так давно в Go добавили новый тип — strings.Builder. Это аналог bytes.Buffer, но при вызове метода String() не происходит повторного выделения памяти и копирования данных.

В отличие от bytes.Buffer, builder не имеет оптимизации малого буфера и, следовательно, предварительно аллоцированной памяти под строку. Если не использовать метод Grow, производительность будет хуже, чем в случае с bytes.Buffer. Несколько регрессий в Go 1.11 вызваны именно этой особенностью (см. CL113235).

В нашем коде, для чистоты эксперимента, мы будем избегать этой ошибки.

func concat2builder(x, y string) string {
var builder strings.Builder
builder.Grow(len(x) + len(y)) // Только эта строка выделяет память
builder.WriteString(x)
builder.WriteString(y)
return builder.String()
}

Оценка производительности: 80.5% (+12.7).

Кодогенерация для конкатенации

Если посмотреть, какой код генерирует компилятор для оператора +, мы увидим вызовы функций concatstring2, concatstring3 и так далее (до concatstring5 включительно).

func concat2codegen(x, y) string { return x + y }
// => CALL runtime.concatstring2(SB)

func concat3codegen(x, y, z) string { return x + y + z }
// => CALL runtime.concatstring3(SB)

Заглянем в сам runtime/string.go:

func concatstring2(buf *tmpBuf, a [2]string) string {
return concatstrings(buf, a[:])
}

func concatstring3(buf *tmpBuf, a [3]string) string {
return concatstrings(buf, a[:])
}

Значит, осталось изучить функцию concatstrings.

Полный листинг доступен ниже под спойлером, а вот высокоуровневое описание:

Параметр buf может быть nil. Этот буфер выделяется компилятором, если строка не "убегает" из области своего определения. Если же строка живёт дольше, чем фрейм, то этот буфер всегда будет nil (как чаще всего и происходит). Однако если этот буфер доступен, получится избежать аллокации в случае, если результат в него влезает (его размер — 32 байта).

Если все строки, кроме одной, пустые, функция вернёт эту строку. Но при этом выделенные на стеке и покидающие свой фрейм строки минуют этой оптимизации, чтобы вызывающая сторона не получила уже освобождённую память.

Далее все строки копируются в новую память.

Полный листинг функции concatstrings

// concatstrings implements a Go string concatenation x+y+z+...
// The operands are passed in the slice a.
// If buf != nil, the compiler has determined that the result does not
// escape the calling function, so the string data can be stored in buf
// if small enough.
func concatstrings(buf *tmpBuf, a []string) string {
idx := 0
l := 0
count := 0
for i, x := range a {
n := len(x)
if n == 0 {
continue
}
if l+n < l {
throw("string concatenation too long")
}
l += n
count++
idx = i
}
if count == 0 {
return ""
}

// If there is just one string and either it is not on the stack
// or our result does not escape the calling frame (buf != nil),
// then we can return that string directly.
if count == 1 && (buf != nil || !stringDataOnStack(a[idx])) {
return a[idx]
}
s, b := rawstringtmp(buf, l)
for _, x := range a {
copy(b, x)
b = b[len(x):]
}
return s
}

Здесь мы видим сразу несколько мест, которые могут быть оптимизированы для частного случая:

buf чаще всего пустой. Когда компилятор не смог доказать, что строку безопасно размещать на стеке, передача лишнего параметра и проверка его на nil внутри функции дают лишь накладные расходы.

Для частного случая при len(a) == 2 нам не нужен цикл и вычисления можно упростить. А это самый распространённый вид конкатенации.

Статистика по использованию конкатенации

При выполнении ./make.bash (сборка Go компилятора и stdlib) видим 445 конкатенаций с двумя операндами:

398 результатов "убегают". В этом случае наша специализация имеет смысл.

47 результатов не покидают своего фрейма.

Итого 89% конкатенаций от двух аргументов попадают пот оптимизацию.

Для утилиты go имеем:

501 вызовов concatstring2

194 вызовов concatstring3

55 вызовов concatstring4

Версия для всех архитектур

Для реализации специализации нам потребуется знать, как в Go представлены строки. Нам важна бинарная совместимость, при этом unsafe.Pointer можно заменить на *byte без каких-либо жертв.

type stringStruct struct {
str *byte
len int
}

Второй важный вывод, который мы можем сделать из рантайма: строки начинают свою жизнь мутабельными. Выделяется участок памяти, на который ссылается []byte, в который записывается содержимое новой строки, и только после этого []byte выбрасывается, а память, на которую он ссылался, сохраняется в stringStruct.

Для тех, кому хочется больше деталей, предлагается изучить функции rawstringtmp и rawstring.

runtime.rawstring

// rawstring allocates storage for a new string. The returned
// string and byte slice both refer to the same storage.
// The storage is not zeroed. Callers should use
// b to set the string contents and then drop b.
func rawstring(size int) (s string, b []byte) {
p := mallocgc(uintptr(size), nil, false)

stringStructOf(&s).str = p
stringStructOf(&s).len = size

*(*slice)(unsafe.Pointer(&b)) = slice{p, size, size}

return
}

Мы можем провернуть примерно то же самое, воспользовавшись тёмной стороной пакета unsafe:

func concat2(x, y string) string {
length := len(x) + len(y)
if length == 0 {
return ""
}
b := make([]byte, length)
copy(b, x)
copy(b[len(x):], y)
return goString(&b[0], length)
}

Мы выделяем []byte, который используем для формирования содержимого новой строки. Затем нам остаётся лишь финализировать строку приведением её к ожидаемому рантаймом представлению. За это отвечает функция goString:

func goString(ptr *byte, length int) string {
s := stringStruct{str: ptr, len: length}
return *(*string)(unsafe.Pointer(&s))
}

Оценка производительности: 91.9% (+10.9).

Версия для AMD64

К сожалению, предыдущая версия функции не имеет оптимизации для конкатенации с пустой строкой, а ещё мы выполняем некоторое количество лишних вычислений из-за невозможности выделить память напрямую, приходится работать со слайсом байт.

Одной из интересных особенностей Go ассемблера является то, что он позволяет вызывать, например, неэкспортируемые функции рантайма. Мы можем вызвать runtime·mallocgc из ассемблерного кода даже если он не является частью пакета runtime. Этим свойством мы и воспользуемся.

Также мы можем проверять принадлежность строк стековой памяти, что делает безопасной оптимизацию возврата одного из аргументов в качестве результата.

Допустим, функция вызвана с аргументами concat2("", "123"). x — пустая строка, и если y не выделен на стеке, мы можем вернуть его в качестве результата конкатенации.

//; Считаем, что x и y имеют тип stringStruct.
//; CX - y.str.
//; SI - y.len.
maybe_return_y:
//; Проверка на вхождения указателя в стек.
MOVQ (TLS), AX //; *g
CMPQ CX, (AX)
JL return_y //; если y_str < g.stack.lo
CMPQ CX, 8(AX)
JGE return_y //; если y_str >= g.stack.hi
JMP concatenate //; y на стеке, нужна новая аллокация
return_y:
MOVQ CX, ret+32(FP) //; stringStruct.len
MOVQ SI, ret+40(FP) //; stringStruct.str
RET

MOVQ (TLS), AX переместит *g в регистр AX. Чтение по нулевому смещению даст поле g.stack.lo, а с 8-го байта начинается g.stack.hi (для 64-битной платформы).

type g struct {
stack struct {
lo uintptr // 0(AX)
hi uintptr // 8(AX)
}
stackguard0 uintptr // 16(AX)
stackguard1 uintptr // 24(AX)
// ... другие поля
}

Тело concatenate выделяет память, заполняет его обеими строками, и возвращает новую строку.

Полный листинг с комментариями

#include "textflag.h"
#include "funcdata.h"

TEXT ·Strings(SB), 0, $48-48
NO_LOCAL_POINTERS // Костыль для избежания ошибки.
MOVQ x+0(FP), DX
MOVQ x+8(FP), DI
MOVQ y+16(FP), CX
MOVQ y+24(FP), SI
TESTQ DI, DI
JZ maybe_return_y // x - пустая строка, попробуем вернуть y
TESTQ SI, SI
JZ maybe_return_x // y - пустая строка, попробуем вернуть x
concatenate:
LEAQ (DI)(SI*1), R8 // len(x) + len(y)
// Выделяем память для новой строки.
MOVQ R8, 0(SP)
MOVQ $0, 8(SP)
MOVB $0, 16(SP)
CALL runtime·mallocgc(SB)
MOVQ 24(SP), AX // Указатель на выделенную память
MOVQ AX, newstr-8(SP)
// Копируем x.
MOVQ x+0(FP), DX
MOVQ x+8(FP), DI
MOVQ AX, 0(SP)
MOVQ DX, 8(SP)
MOVQ DI, 16(SP)
CALL runtime·memmove(SB)
// Копируем y со смещения len(x).
MOVQ x+8(FP), DI
MOVQ y+16(FP), CX
MOVQ y+24(FP), SI
MOVQ newstr-8(SP), AX
LEAQ (AX)(DI*1), BX
MOVQ BX, 0(SP)
MOVQ CX, 8(SP)
MOVQ SI, 16(SP)
CALL runtime·memmove(SB)
// Возврат новой строки.
MOVQ newstr-8(SP), AX
MOVQ x+8(FP), R8
ADDQ y+24(FP), R8
MOVQ AX, ret+32(FP)
MOVQ R8, ret+40(FP)
RET
maybe_return_y:
// Проверка на вхождения указателя в стек.
MOVQ (TLS), AX // *g
CMPQ CX, (AX)
JL return_y // если y_ptr < stk.lo
CMPQ CX, 8(AX)
JGE return_y // если y_ptr >= stk.hi
JMP concatenate // y на стеке, нужна новая аллокация
return_y:
MOVQ CX, ret+32(FP)
MOVQ SI, ret+40(FP)
RET
maybe_return_x:
// Проверка на вхождения указателя в стек.
MOVQ (TLS), AX // *g
CMPQ DX, (AX)
JL return_x // если x_ptr < stk.lo
CMPQ DX, 8(AX)
JGE return_x // если x_ptr >= stk.hi
JMP concatenate // x на стеке, нужна новая аллокация
return_x:
MOVQ DX, ret+32(FP)
MOVQ DI, ret+40(FP)
RET

Если вам интересна природа NO_LOCAL_POINTERS в этом коде, можете почитать Calling a Go function from asm ("fatal error: missing stackmap").

Оценка производительности: 100% (+8.6).

В качестве заключения

Весь код предоставлен в качестве пакета concat.

Готов ли мир к такой быстрой конкатенации? Who knows.

В начале статьи был упомянут CL123256. У него есть несколько путей развития:

Вариадичная специализация для случая, когда компилятором не выделен временный буфер. Меньше прирост на каждый случай, зато покрывает больше видов конкатенации и практически не увеличивает размер кода (как машинного, так и кода на Go).

Больше специализаций для частных случаев. Выше прирост, но больше машинного кода, может навредить кешу инструкций.

Тонны машинного кода, для каждого особого случая и специализированный memmove, на манер того как это сделано в glibc. Здесь в основном встают вопросы целесообразности.

Текущий предложенный вариант ускоряет только наиболее частый и простой случай конкатенации пары строк (арность=2).

Если в Go не примут это изменение, то сравнимого ускорения можно будет добиться с помощью реализации операций над строками в виде сторонней библиотеки. Менее удобно, красиво и элегантно, но зато работает.

Теги:

golang

go

benchmarks

strings

concat

concatenation

performance

optimization

runtime

Хабы:

Assembler

Go

Компиляторы

Программирование

Системное программирование

+28

62

21
+21

143

Карма

0

Рейтинг

Искандер @quasilyte

store.steampowered.com/app/3024370/NebuLeet

Подписаться

Комментарии 21
+21

Публикации

Лучшие за суткиПохожие

A_Tsymbalyuk 13 часов назад

Физика ошибок не прощает. Она догонит тебя на крыше и заставит платить (дважды)

Простой

6 мин

8.1K

Кейс

+40

36

25
+25

BabayMazay 12 часов назад

Самодельные французские радиолампы 1920 г. Часть 3. Разрядная трубка, лампа накаливания

Средний

9 мин

1.5K

Ретроспектива

+33

9

11
+11

Bright_Translate 8 часов назад

Как я от нечего делать замедлил Postgres в 42 000 раз

Средний

11 мин

2.6K

Кейс

Перевод

+27

19

2
+2

lokosst 12 часов назад

Выделенные серверы + Kubernetes: практическое руководство

17 мин

2.4K

Туториал

+21

23

0

butivskiydm 11 часов назад

Моё мини-исследование про продолжительность жизни в России

Простой

2 мин

6.3K

Мнение

+19

17

59
+59

JetHabr 11 часов назад

«Плохие парни работают просто»: пентестеры разбирают реальные кейсы

Средний

9 мин

2.1K

Кейс

+17

19

1
+1

k0mar0v 14 часов назад

HTC Desire HD: история, дизайн и возможности легендарного смартфона

6 мин

2.6K

+17

5

5
+5

MaFrance351 13 часов назад

Домофон Лидер-М. Как скрестить трубку с ключом и всем проиграть

Простой

4 мин

2.5K

+16

5

6
+6

psygalaxy 13 часов назад

Как мы ускорили проверку документации с помощью AI-агента: от боли к решению

Средний

25 мин

1.7K

Обзор

+16

29

9
+9

kubelet 16 часов назад

DNS-хаос, зомби-поды и майнеры в кластере: самые невероятные случаи при работе с Kubernetes

Простой

14 мин

1.2K

Кейс

+16

22

1
+1

AI и майндсет айтишников — выясняем, как изменились IT-работодатели за год
Турбо

Показать еще

Минуточку внимания

Событие

Что ни день – то ивент, если следить за Календарём

Турбо

Полный свайп: оцени, подходит ли тебе работа в IT-ритейле

Событие

Как построить IT-бренд через вирусный контент и юмор

Вопросы и ответы

Trace/breakpoint trap (core dumped)?
LinuxПростой2 ответа

Неточность формулировки в книге или же я не понимаю?
GoПростой2 ответа

Зачем for {select} оборачивать в еще один select с time.Ticker?
GoПростой3 ответа

Какие гарантии на выравнивание адреса указателя?
GoСредний1 ответ

Как поменять env переменную PATH в golang (MacOS)?
GoСредний2 ответа

Больше вопросов на Хабр Q&A

Читают сейчас

Как превратить ноутбук в полноценное рабочее место не хуже стационарного ПК

12K

71
+71

Нашел ЛЯП в игре 5букв от Т-банка, который позволяет со 100% вероятностью угадать скрытое слово

54K

115
+115

Как выйти из IT?.. и пойти слесарем на завод. Моя попыточка дауншифтинга [4\5]

1.4K

11
+11

Моё мини-исследование про продолжительность жизни в России

6.3K

59
+59

Роскомнадзор направил операторам связи РФ письма о необходимости удаления ПО Speedtest Ookla из своей IT-инфраструктуры

21K

100
+100

AI и майндсет айтишников — выясняем, как изменились IT-работодатели за год
Турбо

Истории

История Яндекс Почты

С Днём сисадмина!

Как расти в ИТ: советы, гайды и опыт сеньоров

1 055 450 очков в облаке – попробуй обогнать

Годнота из блогов компаний

Ближайшие события

7 августа

Мем-пати: как построить IT-бренд через вирусный контент и юмор

Москва

Больше событий в календаре

Маркетинг

13 августа

Как повысить эффективность врача в стоматологии на 25% с помощью ИИ?

Онлайн

Больше событий в календаре

Менеджмент

13 августа

Тест-драйв Хабра для маркетологов и пиарщиков

Москва

Больше событий в календаре

Маркетинг

16 августа

«ИТ-летник» — конференция от Совкомбанк Технологий

Казань

Больше событий в календаре

Разработка

Аналитика

3 сентября

«GoCloud Tech 2025» — IT-конференция про облака и AI

Москва • Онлайн

Больше событий в календаре

Разработка

18 – 19 сентября

Конференция по корпоративному онлайн-обучению iSpring Days 2025

Москва • Онлайн

Больше событий в календаре

Администрирование

Менеджмент

Другое

19 сентября

Премия для технологических стартапов Startech.Awards 2025

Москва • Онлайн

Больше событий в календаре

Другое

30 сентября

VII премия в сфере фармацевтического маркетинга и креатива MedMen Awards 2025

Онлайн

Больше событий в календаре

Маркетинг

Другое

30 октября

Премия «Проксима»

Москва

Больше событий в календаре

Маркетинг

Реклама

АО СЕЛЕКТЕЛ

ИНН 7810962785

erid: 2VSb5zDBFAH

1 000 000 стартапам

Кешбэк 30% на год в Selectel!

Ваш аккаунт

Профиль

Трекер

Диалоги

Настройки

ППА

Разделы

Статьи

Новости

Хабы

Компании

Авторы

Песочница

Информация

Устройство сайта

Для авторов

Для компаний

Документы

Соглашение

Конфиденциальность

Услуги

Корпоративный блог

Медийная реклама

Нативные проекты

Образовательные программы

Стартапам

Настройка языкаТехническая поддержка
© 2006–2025, Habr